package interview.huawei.tjt.training.mianshi;

import java.util.*;

/**
 * 给一个二维数组，如
 * [1,3,1],
 * [1,5,1],
 * [4,2,2]
 * 从位置[0][0]开始，只能往右或者往下走，走到右下角，求出路径最小的和
 */
public class Demo {

    private static List<Integer> result = new ArrayList();  // 路径的总值
    private static List<List<Pos>> result1 = new ArrayList();  // 具体路线
    private static List<Pos> path = new LinkedList<>();

    public static void main(String[] args) {

        int[][] nums = new int[][]{{1,3,1},{1,5,1},{4,2,2}};
        helper(0,0,nums,1);
        Collections.sort(result);
//        System.out.println(result1);
        System.out.println(result);
    }

    private static boolean helper ( int startIndexRow, int startIndexCol, int[][] nums, int sum ) {

        path.add(new Pos(startIndexRow,startIndexCol));
        result1.add(new LinkedList<>(path));

        if (startIndexRow == nums.length - 1 && startIndexCol == nums[0].length - 1) {
            result.add(sum);
            return true;
        }

//        if (startIndexRow + 1 < nums.length && startIndexCol + 1 < nums[0].length){
//            return helper(startIndexRow,startIndexCol + 1,nums,sum + nums[startIndexRow][startIndexCol + 1])
//                    || helper(startIndexRow + 1,startIndexCol,nums,sum + nums[startIndexRow + 1][startIndexCol]);
//        }

        // 向右能走时
        if (startIndexRow < nums.length && startIndexCol + 1 < nums[0].length){
            if (helper(startIndexRow,startIndexCol + 1,nums,sum + nums[startIndexRow][startIndexCol + 1])) {
                return true;
            }
        }

        // 向下能走时
        if (startIndexRow + 1 < nums.length && startIndexCol < nums[0].length){
            if (helper(startIndexRow + 1,startIndexCol,nums,sum + nums[startIndexRow + 1][startIndexCol])) {
                return true;
            }
        }

        int x = path.get(path.size() - 1).getX();
        int y = path.get(path.size() - 1).getY();
        path.remove(path.size() - 1);
        sum -= nums[x][y];
        return false;
    }

    private static class Pos {
        int x;
        int y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

}
